package leetcodev1.数组;

public class LeetCode63 {

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length, m = obstacleGrid[0].length;
        int[] f = new int[m];

        f[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    f[j] = 0;
                    continue;
                }
                if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
                    f[j] += f[j - 1];
                }
            }
        }

        return f[m - 1];
    }


    //动态规划
    //定义一个与obstacleGrid相同大小的动态规划数组dict
    //dict的规则
    //1.dict[i][j]的值代表到达当前位置有n种走法
    //2.dict[i][j] = dict[i-1][j] + dict[i][j-1]只能向下 | 向右移动
    //3.obstacleGrid[i][j]=1 dict[i][j]=0
    //4.dict[0][j]和dict[i][0]=1 只有一种走法

    //优化点
    //1.不需要一个打大的dict浪费空间
    //2.不需要额外的遍历数组
    public int uniquePathsWithObstacles1(int[][] obstacleGrid) {
        int height = obstacleGrid.length, width = obstacleGrid[0].length;
        int[][] dict = new int[height][width];//这里可以用一个tmp一维数组代替，减少空间
        int rowInit = 1, columnInit = 1;
        //其实不需要初始化 写的真丑
        for (int i = 0; i < height; i++) {
            if (obstacleGrid[i][0] == 1)
                rowInit = 0;
            dict[i][0] = rowInit;
        }

        for (int j = 0; j < width; j++) {
            if (obstacleGrid[0][j] == 1)
                columnInit = 0;
            dict[0][j] = columnInit;
        }
        for (int i = 1; i < height; i++) {
            for (int j = 1; j < width; j++) {
                if (obstacleGrid[i][j] == 1)
                    continue;
                dict[i][j] = dict[i - 1][j] + dict[i][j - 1];
            }
        }

        return dict[height - 1][width - 1];
    }
}
